package com.xiaojianhx.demo.algorithm.sort;

import java.util.Arrays;

/**
 * Algorithm Sort 02 QuickSort
 * 
 * @author xiaojianhx
 * @version V1.0.0 $ 2021-05-30 00:22:55 init ---- xiaojianhx
 */
public class Algorithm_Sort_02_QuickSort {

    public static void sort(int[] arr) {
        sort(arr, 0, arr.length - 1);
    }

    private static void sort(int[] arr, int low, int hgh) {

        if (low < hgh) {

            var p = partition(arr, low, hgh);

            sort(arr, low, p - 1);
            sort(arr, p + 1, hgh);
        }
    }

    private static int partition(int[] arr, int low, int hgh) {

        var key = arr[low];

        var cycle = 1;

        while (low < hgh) {

            print(arr, low, hgh, key, "第" + cycle + "次循环", "①");

            while (low < hgh && arr[hgh] >= key) {
                hgh--;
            }
            print(arr, low, hgh, key, "第" + cycle + "次循环", "②");

            arr[low] = arr[hgh];
            print(arr, low, hgh, key, "第" + cycle + "次循环", "③");

            while (low < hgh && arr[low] <= key) {
                low++;
            }
            print(arr, low, hgh, key, "第" + cycle + "次循环", "④");

            arr[hgh] = arr[low];
            print(arr, low, hgh, key, "第" + cycle + "次循环", "⑤");

            cycle++;
        }

        print(arr, low, hgh, key, "跳出循环后", "⑥");
        arr[low] = key;

        print(arr, low, hgh, key, "跳出循环后", "⑦");
        System.out.println("------------------------------------");

        return low;
    }

    private static void print(int[] arr, int low, int hgh, int key, String str0, String str1) {
        System.out.println(String.format("%s %s: arr = %s, low = %s, hgh = %s, key = %s", str0, str1, deepToString(arr), low, hgh, key));
    }

    private static String deepToString(int[] arr) {
        return Arrays.toString(arr);
    }
}